/* BinarySearchTree.c -- 树类型的支持函数 */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "BinarySearchTree.h"

// 局部数据类型
typedef struct pair {
    Node * parent;
    Node * child;
} Pair;

// 局部函数的原型

static Node * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode(Node * new_node, Node * root);
static void InOrder(const Node * root, void (* pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Node **ptr);
static void DeleteAllNodes(Node * ptr);

// 函数定义

// 初始化生成树
void InitializeTree(Tree * ptree) {
    ptree->root = NULL;
    ptree->size = 0;
}

// 判断树是否为空
bool TreeIsEmpty(const Tree * ptree) {
    if (ptree->root == NULL)
        return true;
    else
        return false;
}

// 判断树是否满
bool TreeIsFull(const Tree * ptree) {
    if (ptree->size == MAXITEMS)
        return true;
    else
        return false;
}

// 确定树中的项目个数
int TreeItemCount(const Tree * ptree) {
    return ptree->size;
}

// 向树中添加一个项目
bool AddItem(const Item * pi, Tree * ptree) {
    Node * new_node;

    if (TreeIsFull(ptree)) { // 树是否满了
        fprintf(stderr, "Tree is full\n");
        return false;
    }
    if (SeekItem(pi, ptree).child != NULL) { // 判断项目是否重复
        fprintf(stderr, "Attempted to add duplicate item\n");
        return false;
    }
    new_node = MakeNode(pi);   // 创建新节点
    if (new_node == NULL) {
        fprintf(stderr, "Could't creat node\n");
        return false;
    }
    ptree->size++;   // 创建成功，size+1

    if (ptree->root == NULL)    // 树为空，新节点作为根节点
        ptree->root = new_node;
    else                      // 树不为空，新节点加入数中
        AddNode(new_node, ptree->root);
    return true;
}

// 向树中查找一个项目
bool InTree(const Item * pi, const Tree * ptree) {
    return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

// 向树中删除一个项目
bool DeleteItem(const Item * pi, Tree * ptree) {
    Pair look;
    look = SeekItem(pi, ptree);  //查找，返回含两个指针的结构体

    if (look.child == NULL) // look.child为空，说明没有找到要删除的项目
        return false;       // look.child 为目标节点

    if (look.parent == NULL) // look.parent为空 说明目标节点是根节点
        DeleteNode(&ptree->root);
    else if (look.parent->left == look.child)
        DeleteNode(&look.parent->left);
    else
        DeleteNode(&look.parent->right);
    ptree->size--;
    return true;
}

// 通过函数作用于树中的每一个节点的项目
void Traverse(const Tree * ptree, void (* pfun)(Item item)) {
    if (ptree != NULL)
        InOrder(ptree->root, pfun);
}

// 删除所有节点
void DeleteAll(Tree * ptree) {
    if (ptree != NULL)
        DeleteAllNodes(ptree->root);
    ptree->root = NULL;
    ptree->size = 0;
}

// 局部函数的实现

// 创建一个新的节点，并返回新节点地址
static Node * MakeNode(const Item * pi) {
    Node * new_node;

    new_node = (Node *)malloc(sizeof(Node));
    if (new_node != NULL) {
        new_node->item = *pi;  // 项目复制
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

// 判断目标项目在左分支树， 相当于 "<"
static bool ToLeft(const Item * i1, const Item * i2) {
    int comp1;

    if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
        return true;
    else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0)
        return true;
    else
        return false;
}

// 判断目标项目在右分支树， 相当于 ">"
static bool ToRight(const Item * i1, const Item * i2) {
    int comp1;

    if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)
        return true;
    else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0)
        return true;
    else
        return false;
}

// 添加节点
static void AddNode(Node * new_node, Node * root) {
    if (ToLeft(&new_node->item, &root->item)) { // 添加的节点项目大于当前根节点
        if (root->left == NULL)     // 空子树或左子树为空
            root->left = new_node;      // 添加节点到左子树
        else
            AddNode(new_node, root->left);     //  节点不为空，递归
    } else if (ToRight(&new_node->item, &root->item)) { // 添加的节点项目小于当前根节点
        if (root->right == NULL)      // 右子树为空
            root->right = new_node;    // 添加节点到右子树
        else
            AddNode(new_node, root->right);   // 节点不为空，递归
    } else { // 新节点项目相同
        fprintf(stderr, "location error in AddNode() \n");
        exit(EXIT_FAILURE);
    }
}

// 递归遍历二叉树
static void InOrder(const Node * root, void (* pfun)(Item item)) {
    if (root != NULL) {
        InOrder(root->left, pfun);
        (*pfun)(root->item);
        InOrder(root->right, pfun);
    }
}
static Pair SeekItem(const Item * pi, const Tree * ptree) {
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;

    if (look.child == NULL)  // 根节点为空
        return look;
    while (look.child != NULL) {
        if (ToLeft(pi, &(look.child->item))) { // 目标在左分支
            look.parent = look.child;
            look.child = look.child->left;
        } else if (ToRight(pi, &(look.child->item))) { // 目标在左分支
            look.parent = look.child;
            look.child = look.child->right;
        } else       // 前面两种都不是，就是相等的情况
            break;      //look.child是目标节点的地址
    }
    return look;
}
static void DeleteNode(Node **ptr) {
    // ptr是指向目标节点的父节点指针成员的地址
    Node * temp;   // *ptr == temp
    puts((*ptr)->item.petname);

    if ((*ptr)->left == NULL) { // 目标节点的左节点为空/无节点
        temp = *ptr;
        *ptr = (*ptr)->right;  // 右节点取代父节点位置
        free(temp);
    } else if ((*ptr)->right == NULL) { // 目标节点的右节点为空
        temp = *ptr;
        *ptr = (*ptr)->left;  // 左节点取代父节点位置
        free(temp);
    } else { // 目标节点的含有两个节点
        // 循环，沿着左子树的最右分支查找空位置
        for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)
            continue;
        temp->right = (*ptr)->right; // 把目标节点的右子树放到(依附)目标节点左子树的右分支空位置
        temp = *ptr;
        *ptr = (*ptr)->left; // 左子树取代目标节点位置
        free(temp);   // 释放目标节点
    }
}

// 删除所有节点
static void DeleteAllNodes(Node * root) {
    Node * pright;

    if (root != NULL) {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}
